package common.sort;

/**
 * 原理:
 * 1.选中 pivot 中心轴
 * 2.将大于 pivot 的数字放在 pivot 的右边
 * 3.将小于 pivot 的数字放在 pivot 的左边
 * 4.分别重复以上三个步骤
 */
public class QuickSort03 implements Sort {

    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }

        int partitionIndex = partition(array, left, right);
        quickSort(array, left, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, right);
    }

    int partition(int[] array, int left, int right) {
        int pivot = array[left];
        int pivotIndex = left;

        while (left < right) {
            // 向左遍历, 大于等于 pivot, right 左移(大于等于 pivot 放右边)
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 向右遍历, 小于等于 pivot, right 左移(小于等于 pivot 放左边)
            while (left < right && array[left] <= pivot) {
                left++;
            }

            // 如果上面遍历交换，需要写 left - 1 得到中轴位置
            if (left >= right) {
                // 中轴元素位置与当前中轴位置值交换
                int t = array[left];
                array[left] = array[pivotIndex];
                array[pivotIndex] = t;
                break;
            }

            int t = array[right];
            array[right] = array[left];
            array[left] = t;
        }
        return left;
    }
}
